// 链表 的 技巧 与 常用方法
// 1.画图 - 链表的题目大多数都是模拟题，画图能够使模拟过程更加清晰
// 2.引入虚拟头结点 newHead，目的是为了让尾指针具备一般性，一个循环搞定代码
// 3.不吝啬空间，敢于定义变量 prev, next等：prev - 前边链的尾指针  next - 后边链的头指针 有头有尾，不怕链断
// 4.快慢双指针 - 判断环，找环的入口，找链表中的倒数第 n 个节点
// 5.创建新节点
// 6.尾插法 - 定义尾节点 tail，维护尾节点
// 7.头插法 - 引入虚拟头结点 newHead: node -> newHead.next, newHead.next -> node

// 例题 2：
// 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
// 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
//
//        示例 1：
//
//        输入：head = [1,2,3,4]
//        输出：[2,1,4,3]
//        示例 2：
//
//        输入：head = []
//        输出：[]
//        示例 3：
//
//        输入：head = [1]
//        输出：[1]
//
//
//        提示：
//
//        链表中节点的数目在范围 [0, 100] 内
//        0 <= Node.val <= 100

// 解题思路：
// 直接模拟题目中交换链表节点的过程即可
// 唯一的难点就是交换过程中可能会导致链表断开
// 因此我们不能吝啬空间，需要大胆定义：
// prev - 表示前面链的尾指针
// next - 后面链的头指针
// 为了方便能够你一个循环搞定代码，因此需要引入虚拟头结点 newHead
// prev = newHead，这样的话，才能让 prev 始终都能表示前面链的尾指针，从而不失一般性
// 交换两个节点，然后移动 4 指针，即可解决

public class SwapPairs {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode newHead = new ListNode();
        ListNode prev = newHead;
        ListNode cur1 = head;
        ListNode cur2 = cur1.next;
        ListNode next = cur2.next;
        while(cur1 != null && cur2 != null){
            // 交换位置
            prev.next = cur2;
            cur2.next = cur1;
            cur1.next = next;
            // 重新布置 4 指针
            prev = cur1;
            cur1 = next;
            if(cur1 != null) {
                cur2 = cur1.next;
                if(cur2 != null) next = cur2.next;
            }
        }
        return newHead.next;
    }
}
